import java.util.*;
public class Leetcode {
}

//牛客:【模板】01背包
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        int[] dp1 = new int[V+1];

        for(int i = 1; i <= n; i++){
            for(int j = V; j >= v[i]; j--){
                dp1[j] = Math.max(dp1[j] , dp1[j-v[i]] + w[i]);
            }
        }

        System.out.println(dp1[V]);

        int[] dp2 = new int[V+1];

        for(int j = 1; j <= V; j++) dp2[j] = -1;

        for(int i = 1; i <= n ; i++){
            for(int j = V; j >= v[i]; j--){
                if(dp2[j-v[i]] != -1) dp2[j] = Math.max(dp2[j] , dp2[j-v[i]] + w[i]);
            }
        }


        System.out.println(dp2[V] == -1 ? 0 : dp2[V]);

    }
}


//滚动数组优化
// 注意类名必须为 Main, 不要有任何 package xxx 信息
class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), V = in.nextInt();
        int[] v = new int[n+1];
        int[] w = new int[n+1];
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }

        int[] dp1 = new int[V+1];

        for(int i = 1; i <= n; i++){
            for(int j = V; j >= v[i]; j--){
                dp1[j] = Math.max(dp1[j] , dp1[j-v[i]] + w[i]);
            }
        }

        System.out.println(dp1[V]);

        int[] dp2 = new int[V+1];

        for(int j = 1; j <= V; j++) dp2[j] = -1;

        for(int i = 1; i <= n ; i++){
            for(int j = V; j >= v[i]; j--){
                if(dp2[j-v[i]] != -1) dp2[j] = Math.max(dp2[j] , dp2[j-v[i]] + w[i]);
            }
        }


        System.out.println(dp2[V] == -1 ? 0 : dp2[V]);

    }
}

//leetcode:416:分割等和子集
class Solution1 {
    public boolean canPartition(int[] nums) {
        int n = nums.length , sum = 0;
        //计算数组元素的总和
        for(int x : nums) sum += x;
        //如果总和为奇数，无法进行等分，返回false
        if(sum % 2 == 1) return false;
        //得到总和的中间值
        int aim = sum/2;

        //创建一个dp表，表示，前i个元素是否能够凑成j
        boolean[][] dp = new boolean[n+1][aim+1];
        //如果j为0，我们都不选就可以凑成0
        for(int i = 0; i <= n; i++) dp[i][0] = true;

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= aim; j++){
                //如果不选i位置的元素，就要到前i-1个元素里判断是否能够凑成j
                dp[i][j] = dp[i-1][j];
                //如果选i位置的元素，我们就要判断j是否还能有剩余
                if(j >= nums[i-1])
                    //如果有就要判断我们前i-1个元素是否能够凑成j-nums[i-1]的值
                    //然后判断这两种情况是否有一种能够凑成j,如果能就赋值为true
                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
            }
        }
        return dp[n][aim];
    }
}

//滚动数组优化
class Solution2 {
    public boolean canPartition(int[] nums) {
        int n = nums.length , sum = 0;
        for(int x : nums) sum += x;
        if(sum % 2 == 1) return false;

        int aim = sum/2;

        boolean[] dp = new boolean[aim+1];
        dp[0] = true;

        for(int i = 1; i <= n; i++){
            for(int j = aim; j >= nums[i-1]; j--){
                dp[j] = dp[j] || dp[j-nums[i-1]];
            }
        }
        return dp[aim];
    }
}